package practice_2025_8_29;

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 记录字符个数, 双指针
        Map<Character, Integer> hash = new HashMap<>();
        int max = 0;
        for(int left = 0, right = 0; right < s.length(); right++) {
            // 入窗口
            char in = s.charAt(right);
            hash.put(in, hash.getOrDefault(in, 0) + 1);
            // 出窗口
            while (hash.get(in) > 1) {
                char out = s.charAt(left);
                hash.put(out, hash.getOrDefault(out, 0) - 1);
                left++;
            }
            // 更新
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 1. root = p 或 root = q 或 root 分别在root的左子树和右子树 -> root
        // 2. 都在 root的左子树 -> 继续在左子树找
        // 3. 都在 root 的右子树 -> 继续在右子树找
        if(root == p || root == q) {
            return root;
        }
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}